Tên của quốc gia này bắt nguồn từ từ tiếng Hy Lạp Μακεδονία (Makedonía),[8][9] tên gọi về một quốc gia của người Macedonia cổ đại. Tên người Macedonia, Μακεδόνες (Makedónes), bắt nguồn từ một chữ của tiếng Hy Lạp cổ đại là μακεδνός (makednós), có nghĩa là "cao, thon nhọn",[10] cũng cùng chung nguồn gốc với danh từ μάκρος (mákros), nghĩa là "chiều dài" trong cả tiếng Hy Lạp cổ đại và hiện đại.[11] Tên này được cho là có nghĩa nguyên là "người vùng cao nguyên" hay "người cao",[9][12][13] có thể ám chỉ đến tầm vóc cao lớn của người Macedonia cổ đại hoặc nói đến địa hình vùng núi cao nơi họ sinh sống.

Ngày 17/06/2018, Người đứng đầu Chính phủ Cộng hoà Macedonia là Thủ tướng Zoran Zaev gặp người đồng cấp Hy Lạp là Thủ tướng Alexis Tsipras tại hồ Prespa, ngay khu biên giới giữa ba nước Hy Lạp, Macedonia và Albania, để cùng ký một thoả thuận nêu rõ việc Cộng hoà Macedonia sẽ đổi tên thành Cộng hoà Bắc Macedonia, tránh trùng tên gọi với một tỉnh ở phía Bắc của Hy Lạp.

Để thoả thuận đi vào thực tế, nó sẽ phải được thông qua tại Quốc hội hai quốc gia và được người dân chấp nhận trong một cuộc trưng cầu dân ý tại Macedonia. Hiệp định vừa ký kết mở đường cho Macedonia có cơ hội gia nhập Tổ chức Hiệp ước Bắc Đại Tây Dương (NATO) và bắt đầu tiến hành đàm phán gia nhập EU. Đây là những nguyện vọng của Macedonia từng bị chính quyền Athens lấy tư cách là thành viên EU ngăn cản.

Tháng 1 năm 2019, Hiệp định chính thức được Quốc hội hai quốc gia thông qua.[14] Ngày 12 tháng 2 năm 2019, hai quốc gia tuyên bố rằng thỏa thuận đổi tên chính thức của Cộng hòa Macedonia thành Cộng hòa Bắc Macedonia bắt đầu có hiệu lực.[15]